package com.sicheng.lc.周赛.分类.栈.单调栈or单调队列;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/11 22:41
 */
@SuppressWarnings("all")
public class 元素值大于变化阈值的子数组 {
    //https://leetcode.cn/problems/subarray-with-elements-greater-than-varying-threshold/
    static int N = (int) 1e5;
    static int[] left = new int[N];
    static int[] right = new int[N];
    static ArrayDeque<Integer> leftStack = new ArrayDeque<>(500);
    static ArrayDeque<Integer> rightStack = new ArrayDeque<>(500);

    {
        leftStack.clear();
        rightStack.clear();
        Arrays.fill(left, 0);
        Arrays.fill(right, N);
    }

    public int validSubarraySize(int[] nums, int threshold) {

        for (int i = 0; i < nums.length; i++) {
            int j = nums.length - i - 1;

            while (!leftStack.isEmpty() && nums[i] <= nums[leftStack.peek()])
                leftStack.pop();

            while (!rightStack.isEmpty() && nums[j] < nums[rightStack.peek()])
                rightStack.pop();

            if (!leftStack.isEmpty())
                left[i] = leftStack.peek() + 1;

            if (!rightStack.isEmpty())
                right[j] = rightStack.peek() - 1;

            leftStack.push(i);
            rightStack.push(j);
        }

        for (int i = 0; i < nums.length; i++) {
            int L = left[i], R = Math.min(right[i], nums.length - 1);
            if (nums[i] > threshold / (R - L + 1))
                return R - L + 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        元素值大于变化阈值的子数组 s = new 元素值大于变化阈值的子数组();
        int[] nums = {1, 4, 2};
        System.out.println(s.validSubarraySize(nums, 6));
    }
}
